﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PS.DataTypes
{
    // http://blogs.msdn.com/b/ericlippert/archive/2007/10/08/path-finding-using-a-in-c-3-0-part-three.aspx
    public class PriorityQueue<P, V>
    {
        private SortedDictionary<P, Queue<V>> list = new SortedDictionary<P, Queue<V>>();

        public void Enqueue(P priority, V value)
        {
            Queue<V> q;
            if (!list.TryGetValue(priority, out q))
            {
                q = new Queue<V>();
                list.Add(priority, q);
            }
            q.Enqueue(value);
        }

        public V Dequeue()
        {
            // will throw if there isn’t any first element!
            var pair = list.First();
            var v = pair.Value.Dequeue();
            if (pair.Value.Count == 0) // nothing left of the top priority.
                list.Remove(pair.Key);
            return v;
        }

        public bool IsEmpty
        {
            get { return !list.Any(); }
        }

        public void Update(P oldPriority, P newPriority, V value)
        {
            Queue<V> q;
            list.TryGetValue(oldPriority, out q);

            Queue<V> b = new Queue<V>();

            foreach (V v in q)
            {
                if (v.Equals(value))
                {
                    Enqueue(newPriority, value);
                }
                else
                {
                    b.Enqueue(v);
                }
            }

            int counter = q.Count;
            for (int i = 0; i < counter; i++)
            {
                q.Dequeue();
            }

            foreach (V v in b)
            {
                q.Enqueue(v);
            }
        }
    }
}
